Search results for "Complexity function"
showing 4 items of 4 documents
A NEW COMPLEXITY FUNCTION FOR WORDS BASED ON PERIODICITY
2013
Motivated by the extension of the critical factorization theorem to infinite words, we study the (local) periodicity function, i.e. the function that, for any position in a word, gives the size of the shortest square centered in that position. We prove that this function characterizes any binary word up to exchange of letters. We then introduce a new complexity function for words (the periodicity complexity) that, for any position in the word, gives the average value of the periodicity function up to that position. The new complexity function is independent from the other commonly used complexity measures as, for instance, the factor complexity. Indeed, whereas any infinite word with bound…
On a Conjecture on Bidimensional Words
2003
We prove that, given a double sequence w over the alphabet A (i.e. a mapping from Z2 to A), if there exists a pair (n0, m0) ∈ Z2 such that pw(n0, m0) < 1/100n0m0, then w has a periodicity vector, where pw is the complexity function in rectangles of w.
Cyclic Complexity of Words
2014
We introduce and study a complexity function on words $c_x(n),$ called \emph{cyclic complexity}, which counts the number of conjugacy classes of factors of length $n$ of an infinite word $x.$ We extend the well-known Morse-Hedlund theorem to the setting of cyclic complexity by showing that a word is ultimately periodic if and only if it has bounded cyclic complexity. Unlike most complexity functions, cyclic complexity distinguishes between Sturmian words of different slopes. We prove that if $x$ is a Sturmian word and $y$ is a word having the same cyclic complexity of $x,$ then up to renaming letters, $x$ and $y$ have the same set of factors. In particular, $y$ is also Sturmian of slope equ…